The Evaluation Function

For the shallow search, each leaf node in the tree (at depth 3) corresponds to two playing field states – b₁ and b₁’. For the deep search, each leaf node (at depth 7) corresponds to two playing field states – b₂ and b₂’. The various states are defined below in the order of occurrence:

b0	Current playing field (at the root of the tree).
b1	Playing field with the current (first) tetrad in a final resting position prior to possible line completion.
b1’	Playing field b1 with the line completion operation applied.
b2	Playing field with the next (second) tetrad in a final resting position prior to possible line completion.
b2’	Playing field b2 with the line completion operation applied.

The evaluation function used is (given states b and b’) a weighted sum of eight functions that return nonnegative values:

E(b, b’) = w₁F₁(b) + w₂F₂(b) + w₃F₃(b) + w₄F₄(b’) + w₅F₅(b’) + w₆F₆(b’) + w₇F₇(b’) + w₈F₈(b’)

The goal of the shallow search is to maximize E(b₁,b₁’). The goal of the deep search is to maximize E(b₂,b₂’).

Notes:

· The first 3 functions operate on state b rather than b’ because they evaluate the final placement of the tetrad. If lines are completed, then all four tetrad squares no longer exist in state b’. The remainder of the functions operate on state b’ because it is the true final state resulting from a particular sequence of moves. · If no lines are completed by the placement of the tetrad, then b = b’. · For the deep search, the first 3 functions act only on the second tetrad, and F5 counts the total number of lines completed (by both tetrads) from b0 to b2’.

The eight functions compute features of the playing field state. I selected eight features that I felt were important to evaluate when deciding where to place a tetrad. I originally had many detailed features in mind, but the eight general features seem to be sufficient for exhibiting much better playing ability than I had expected (see Results). Below are the definitions of the eight functions:

F₁ = Maximum Depth of Tetrad Squares

This value is the height of the deepest (lowest) of the tetrad’s four squares when it lands in its final position (prior to possible line completion). The value corresponds to the row number, where 1 is the top row and 20 is the bottom row.

F₂ = Minimum Depth of Tetrad Squares

This value is the height of the shallowest (highest) of the tetrad’s four squares when it lands in its final position (prior to possible line completion). The value corresponds to the row number, where 1 is the top row and 20 is the bottom row.

F₃ = Average Depth of Tetrad Squares

This value is the average height of the tetrad’s four squares when it lands in its final position (prior to possible line completion). The value for each of the four squares corresponds to the row number, where 1 is the top row and 20 is the bottom row. The sum of these four values is divided by four to obtain the average depth of the tetrad.

F₄ = Ø (Number of Holes)

This value is the "negation" of the number of holes on the playing field after the tetrad has landed and after possible line completion. (A hole is a blank square that has at least one filled square above it in the same column.) In order to have F₄ evaluate to a nonnegative number, the number of holes is "negated" by subtracting the value from 200 (the total number of squares on the playing field – 10 x 20). Thus, this value is the number of non-hole squares on the playing field.

F₅ = Number of Lines Completed

This value is the number of lines (if any) that become completed (and disappear) during the transition from b₀ to the final state (b₁’ or b₂’). This number ranges from 0 to 4 for the shallow search, or 0 to 8 for the deep search.

F₆ = Surface Smoothness

The hole prevention encouraged by F₄ may lead to high stacks of filled squares with deep canyons that can only be filled by red tetrads. The goal of keeping a smooth "surface" (the topmost filled block in each column) is to counteract this (which normally involves creating some holes), as well as providing smooth landing spots for tetrads that may create holes if placed on a "rough" surface. Thus, the optimal TETRIS player must find the right balance between hole prevention and surface smoothness. The value for this feature is the "negation" of surface roughness (200 – surface roughness), where surface roughness is the sum of surface height differences in adjacent columns. More specifically,

Surface roughness =

(h₂ – h₁) + |h₂ – h₃| + |h₃ – h₄| + |h₄ – h₅| + |h₅ – h₆| + |h₆ – h₇| + |h₇ – h₈| + |h₈ – h₉| + (h₉ – h₁₀)

Where h_i is the height (row number, from 1 at the top to 20 at the bottom) of column i, 1 £ i £ 10, h₁ is the leftmost column and h₁₀ is the rightmost column. Note that the definition encourages height to accumulate against the walls of the playing field. This is intentional, because high stacks of squares along the walls do not break up the playing field as stacks elsewhere do.

F₇ = Ø (Squares Above Holes)

For each column that has a hole, calculate (height of lowest space – height of topmost hole), where height is the row number, from 1 at the top to 20 at the bottom. (A space is a blank square that is not a hole.) Sum these values and "negate" by subtracting it from 200. This is the value for F₇.

F₈ = Spaces Adjacent to Holes

This feature is intended to make it more possible to slide tetrads into holes and can be thought of as "avoidance of hole trapping." Its value is the sum of the number of consecutive spaces (blank squares that aren’t holes) to the immediate left and right for each hole on the playing field. Because of its definition, however, terrible play can result if this feature is weighted too heavily – the more holes on the playing field, the higher F₈ is likely to be.